

import java.util.Iterator;
import java.util.function.Consumer;

/*
单向链表（带哨兵）：
差距只是多了一个哨兵节点，
在插入的时候不用考虑节点返回null，
以及遍历的时候需要排除哨兵节点
 */
public class DanXiangLianBiaoShaoBin implements Iterable<Integer> { //整体
    private Node head = new Node(666, null); //头指针指向哨兵节点

    /*
     *  节点类
     * */
    private static class Node {  //内部类（不用对外暴露内部结构）
        int value; //值
        Node next; //下一个节点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }


    //头茬
    public void addFirst(int value) {
        // 带哨兵 直接用insert方法即可
        insert(0, value);
    }

    //遍历
    public void loop1(Consumer<Integer> consumer) {
        Node p = head.next;  //初始应该指向哨兵 遍历的起点变了
        while (p != null) {
            consumer.accept(p.value);
            p = p.next; //处理完当前节点之后在在指向下一个节点
        }
    }

    public void loop2(Consumer<Integer> consumer) {
        for (Node p = head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    @Override
    public Iterator<Integer> iterator() {


        return new Iterator<Integer>() {
            Node p = head.next;

            @Override
            public boolean hasNext() { //是否有下一个元素
                return p != null;
            }

            @Override
            public Integer next() { //返回当前元素并指向，下一个元素
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }

    //查找最后一个节点
    private Node findLast() {
        Node p;
        //head一直都存在一个哨兵节点，不可能为null了
//       if (head == null){ //空链表
//       return null;
//       }
        for (p = head; p.next != null; p = p.next) { //问题，如果head为null ，则p.next 报空指针了

        }
        return p;
    }

    //尾插
    public void addLast(int value) {
        Node last = findLast();
        //不存在这个可能了
//       if(last == null) {
//           addFirst(value);
//           return ;
//       }
        last.next = new Node(value, null);

    }


    // 查找Node 节点
    private Node findeNode(int index) {
        int i = -1; //哨兵的索引
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null; //没有找到
    }

    //对外返回索引节点的值
    public int get(int index) {
        Node node = findeNode(index);
        if (node == null) {
            IllegalIndex(index);
        }
        return node.value;
    }

    // 向索引位置加入新节点
    public void insert(int index, int value) {
        //带哨兵简化了
//        if (index == 0) {
//            addFirst(value);
//            return;
//        }
        Node prev = findeNode(index - 1);//找到上一个节点
        if (prev == null) IllegalIndex(index);
        //创建一个新节点，让perv指向下一个节点的next指针给到新节点，然后自己又指向这个创建的节点
        prev.next = new Node(value, prev.next);
    }

    private static IllegalArgumentException IllegalIndex(int index) {
        throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index)); //不合法参数
    }

    public int size() {
        int i = -1;
        for (Node p = head; p != null; p = p.next, i++) {

        }

        return i;
    }

    // 删除第一个节点
    public void removeFirst() {
        remove(0);
    }

    //根据index删除
    public void remove(int index) {
//       if (index == 0) {
//           removeFirst();
//           return;
//       }
        Node prev = findeNode(index - 1); //找到上一个节点
        if (prev == null) throw IllegalIndex(index); //没有查到节点（前一个结点差不到，那么后面也不会存在）
        Node removed = prev.next; //将要被删除的节点
        //这个问题出现在删除的节点的上一个节点是最后一个节点的情况(前一个能找到，但是待删除节点不存在)
        if (removed == null) throw IllegalIndex(index);

        prev.next = removed.next;

    }

    // 递归遍历
    // 1.遍历
    public void loop() {
        // 调用recursion();
        recursion(head.next); // 哨兵节点的下一个节点作为起始位
    }

    // 递归
    private void recursion(Node curr) { // 某个节点要进行的操作
        if (curr == null) {
            return;
        }
        System.out.println(curr.value);
        recursion(curr.next);
    }



}


